
//1.合并两个有序链表
//思路1:1.双指针移动；2.剩余的链表做拼接操作；
//思路2:递归实现

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct ListNode {
      int val;
      struct ListNode *next;
      ListNode(int x) :
            val(x), next(NULL) {
      }
};

class Solution1 {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* vhead=new ListNode(-1); //一个技巧 初始化虚拟虚拟头结点，使每一个结点都有一个前驱结点便于循环
        ListNode *newhead=vhead;
        while(pHead1&&pHead2)//终止条件 一个链表为空
        {
            if(pHead1->val<=pHead2->val) //哪个链表头节点小从哪个链表拿
            {
                newhead->next=pHead1; //取节点
                pHead1=pHead1->next;//后移对应链表
            }
            else//同理
            {
                newhead->next=pHead2;
                pHead2=pHead2->next;
            }
            newhead=newhead->next;//将新链表后移
        }
        if(pHead2==nullptr) //将剩余的链表拼在后面
            newhead->next=pHead1;
        if(pHead1==nullptr)
            newhead->next=pHead2;
        return vhead->next;
    }
};

class Solution2 {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //一个已经为空了，返回另一个
        if(pHead1 == NULL)
            return pHead2;
        if(pHead2 == NULL)
            return pHead1;
        //先用较小的值的节点
        if(pHead1->val <= pHead2->val){
            //递归往下
            pHead1->next = Merge(pHead1->next, pHead2);
            return pHead1;
        }else{
            //递归往下
            pHead2->next = Merge(pHead1, pHead2->next);
            return pHead2;
        }
    }
};